﻿#region

using Common.DataStructures.Heap;

#endregion

namespace AdvancedTraining.Lesson35;

/// <summary>
/// 来自网易的路径最小代价问题
/// </summary>
/// <remarks>
/// 地图规则：
/// - map[i,j] == 0，代表(i,j)是海洋，渡过的话代价是2
/// - map[i,j] == 1，代表(i,j)是陆地，渡过的话代价是1
/// - map[i,j] == 2，代表(i,j)是障碍，无法渡过
/// 每一步上、下、左、右都能走，返回从左上角走到右下角最小代价是多少，如果无法到达返回-1
///
/// 算法思路：
/// 使用Dijkstra算法的最小堆实现，优先扩展代价最小的路径
/// 时间复杂度：O(N*M*log(N*M))，其中N和M是地图的行数和列数
/// 空间复杂度：O(N*M)，用于visited数组
/// </remarks>
public class WalkToEnd
{
    /// <summary>
    /// 计算从左上角到右下角的最小代价
    /// </summary>
    /// <param name="map">地图矩阵</param>
    /// <returns>最小代价，如果无法到达返回-1</returns>
    public static int MinCost(int[,] map)
    {
        if (map[0, 0] == 2) return -1;
        var n = map.GetLength(0);
        var m = map.GetLength(1);
        var minHeap = new Heap<Node>((a, b) => a.Cost - b.Cost);
        var visited = new bool[n, m];
        Add(map, 0, 0, 0, minHeap, visited);
        while (!minHeap.isEmpty)
        {
            var cur = minHeap.Pop();
            if (cur.Row == n - 1 && cur.Col == m - 1) return cur.Cost;
            Add(map, cur.Row - 1, cur.Col, cur.Cost, minHeap, visited);
            Add(map, cur.Row + 1, cur.Col, cur.Cost, minHeap, visited);
            Add(map, cur.Row, cur.Col - 1, cur.Cost, minHeap, visited);
            Add(map, cur.Row, cur.Col + 1, cur.Cost, minHeap, visited);
        }

        return -1;
    }

    /// <summary>
    /// 向最小堆中添加可达节点
    /// </summary>
    /// <param name="m">地图矩阵</param>
    /// <param name="i">行坐标</param>
    /// <param name="j">列坐标</param>
    /// <param name="pre">到达该位置的累积代价</param>
    /// <param name="heap">最小堆</param>
    /// <param name="visited">访问标记矩阵</param>
    private static void Add(int[,] m, int i, int j, int pre, Heap<Node> heap, bool[,] visited)
    {
        // 修复数组维度访问错误：对于二维数组int[,]，应使用GetLength(0)获取行数，而不是Length
        if (i >= 0 && i < m.GetLength(0) && j >= 0 && j < m.GetLength(1) && m[i, j] != 2 && !visited[i, j])
        {
            // 根据地形计算代价：海洋(0)代价为2，陆地(1)代价为1
            heap.Push(new Node(i, j, pre + (m[i, j] == 0 ? 2 : 1)));
            visited[i, j] = true;
        }
    }

    /// <summary>
    /// 表示路径节点的类，用于在最小堆中存储位置信息和代价
    /// </summary>
    private class Node(int a, int b, int c)
    {
        /// <summary>
        /// 行坐标
        /// </summary>
        public readonly int Row = a;

        /// <summary>
        /// 列坐标
        /// </summary>
        public readonly int Col = b;

        /// <summary>
        /// 从起点到该位置的累积代价
        /// </summary>
        public readonly int Cost = c;
    }

    /// <summary>
    /// 运行测试用例
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("=== WalkToEnd 测试 ===");

        // 测试用例1：简单可达路径
        var map1 = new int[,]
        {
            { 1, 1 },
            { 1, 1 }
        };
        Console.WriteLine($"测试1 - 简单可达路径: 期望=3, 实际={MinCost(map1)}");

        // 测试用例2：包含海洋的路径
        var map2 = new int[,]
        {
            { 1, 0, 1 },
            { 1, 1, 1 }
        };
        Console.WriteLine($"测试2 - 包含海洋的路径: 期望=4, 实际={MinCost(map2)}");

        // 测试用例3：起点是障碍
        var map3 = new int[,]
        {
            { 2, 1 },
            { 1, 1 }
        };
        Console.WriteLine($"测试3 - 起点是障碍: 期望=-1, 实际={MinCost(map3)}");

        // 测试用例4：无法到达的情况
        var map4 = new int[,]
        {
            { 1, 2 },
            { 2, 1 }
        };
        Console.WriteLine($"测试4 - 无法到达的情况: 期望=-1, 实际={MinCost(map4)}");

        // 测试用例5：复杂地形
        var map5 = new int[,]
        {
            { 1, 0, 2, 1 },
            { 1, 1, 1, 0 },
            { 2, 1, 0, 1 }
        };
        Console.WriteLine($"测试5 - 复杂地形: 期望=7, 实际={MinCost(map5)}");

        // 测试用例6：单格地图
        var map6 = new int[,]
        {
            { 1 }
        };
        Console.WriteLine($"测试6 - 单格地图: 期望=1, 实际={MinCost(map6)}");

        Console.WriteLine("=== 测试完成 ===");
    }
}